1. 题目描述（简单难度）

[success] 101. 对称二叉树

2. 解法一：使用队列迭代方法

首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return check(root,root);
    }

    public boolean check(TreeNode u,TreeNode v){
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerLast(u);
        deque.offerLast(v);
        while(!deque.isEmpty()){
        u =  deque.pollFirst();
        v =  deque.pollFirst();
        if(null == u && null == v){
            continue;
        }
        if(null == u || null == v){
            return false;
        }
        if(u.val != v.val){
            return false;
        }
         deque.offerLast(u.left);
         deque.offerLast(v.right);

         deque.offerLast(u.right);
         deque.offerLast(v.left);
        }
        return true;
    }
}

3. 解法二：使用递归

递归结束条件：

都为空指针则返回 true 只有一个为空则返回 false 递归过程：

• 判断两个指针当前节点值是否相等
• 判断 A 的右子树与 B 的左子树是否对称
• 判断 A 的左子树与 B 的右子树是否对称

短路：

在递归判断过程中存在短路现象，也就是做 与 操作时，如果前面的值返回 false 则后面的不再进行计算

时间复杂度：O(n)O(n)

class Solution {
    public boolean isSymmetric(TreeNode root) {
      return check(root,root);
    }

    public boolean check(TreeNode u,TreeNode v){
        if(u == null && v == null){
            return true;
        }
        if(u == null || v == null){
            return false;
        }
        if(u.val != v.val){
            return false;
        }
        return check(u.left,v.right) && check(u.right,v.left);
    }
}